//==========================================================================
// Copyright (c) 2000-2008,  Elastos, Inc.  All Rights Reserved.
//==========================================================================
#include <core.h>
#include <_hal.h>
#include <mdetect.h>

#ifdef  MUTEX_DEADLOCK_DETECT

typedef struct MutexDetectionNode : public DLinkNode
{
    DzMutex *pMutex;
} MutexDetectionNode;

const UInt32 c_dlMDetectNodeMax = 1000;
const UInt32 c_dlMutexMax = 1000;
const UInt32 c_dlThreadMax = 1000;

MutexDetectionNode g_mutexDetection[c_dlMDetectNodeMax];

DLinkNode g_freeMutexListHead;
DLinkNode g_usedMutexListHead;

DzMutex *g_mutexDect[c_dlMutexMax];
Thread *g_threadDect[c_dlThreadMax];

UInt32 g_uMutexNum = 0;
UInt32 g_uThreadNum = 0;

void NumberedCurrentMutexs();
void NumberedDetectionThreads();
Boolean IsInThreadDectPool(Thread *pThread);
UInt32 GetMutexNum(DzMutex *pMutex);
UInt32 GetDectThreadNum(Thread *pThread);
DzMutex *GetRequestedMutex(Thread *pThread);
void OutputDeadLockInfo(UInt32 *pArr);

EXTERN void MutexDeadLockDetection(DzMutex *pCurMutex)
{
    InsertIntoMutexList(pCurMutex);

    if (g_usedMutexListHead.IsEmpty()) return;

    if (g_uMutexNum > c_dlMutexMax) return;
    NumberedCurrentMutexs();
    if (g_uMutexNum >= c_dlMutexMax) {
        return;
    }

    if (g_uThreadNum > c_dlThreadMax) return;
    NumberedDetectionThreads();
    if (g_uThreadNum >= c_dlThreadMax) {
        return;
    }

//    kprintf("\n");
//    UInt32 i;
//    for (i = 0; i < g_uMutexNum; i++)
//        kprintf("mutex[%d] = %x, ", i, g_mutexDect[i]);
//
//    kprintf("\n");
//    for (i = 0; i < g_uThreadNum; i++)
//        kprintf("thread[%d] = %x, ", i, g_threadDect[i]);
//    kprintf("\n");

    UInt32 *dectCir;
    dectCir = (UInt32 *)_alloca(
        sizeof(UInt32) * (g_uMutexNum + g_uThreadNum + 1));

    dectCir[1] = 0; //current thread num g_threadDect[0]
    dectCir[2] = GetMutexNum(pCurMutex); // current thread requested mutex;
    assert(dectCir[2] < c_dlMutexMax);
    if (NULL == pCurMutex->GetOwner()) return;

    UInt32 uIndex = 3, nMutexNum = c_dlMutexMax, nThreadNum = c_dlThreadMax;
    DzMutex *pMutex = pCurMutex;
    Thread *pThread = pCurMutex->GetOwner();
    if (pThread == g_threadDect[0]) return;

    do {
        nThreadNum = GetDectThreadNum(pThread);
        assert(nThreadNum < c_dlThreadMax);
        dectCir[uIndex++] = nThreadNum;
        if (pThread == g_threadDect[0]) {
            dectCir[0] = uIndex;
            kprintf("\n****************** DEAD LOCK ******************\n");
            OutputDeadLockInfo(dectCir);
            kprintf("\n***********************************************\n");
            return;
        }

        pMutex = GetRequestedMutex(pThread);
        if (pMutex == NULL) return;
        nMutexNum = GetMutexNum(pMutex);
        assert(nMutexNum < c_dlMutexMax);
        dectCir[uIndex++] = nMutexNum;

        if (pThread == pMutex->GetOwner()) return;
        pThread = pMutex->GetOwner();
        if (NULL == pThread) return;
    } while (TRUE);
}

EXTERN void InsertIntoMutexList(DzMutex *pMutex)
{
    NumberedCurrentMutexs();
    if (g_uMutexNum >= c_dlMutexMax) {
        return;
    }

    MutexDetectionNode *pmd;
    ForEachDLinkNode(MutexDetectionNode *, pmd, &g_usedMutexListHead)
    {
        if (pmd->pMutex == pMutex) return;
    }

    MutexDetectionNode *pMutexNode = \
            (MutexDetectionNode *)g_freeMutexListHead.First();
    pMutexNode->Detach();

    pMutexNode->pMutex = pMutex;
    g_usedMutexListHead.InsertFirst(pMutexNode);
}

EXTERN _ELASTOS Boolean DetachFromMutexList(DzMutex *pMutex)
{
    assert(pMutex != NULL);

    MutexDetectionNode *pMutexNode;

    ForEachDLinkNode(MutexDetectionNode *, pMutexNode, &g_usedMutexListHead) {
        if (pMutexNode->pMutex == pMutex) {
            pMutexNode->Detach();
            g_freeMutexListHead.InsertLast(pMutexNode);

            return TRUE;
        }
    }

    return FALSE;
}

void NumberedCurrentMutexs()
{
    MutexDetectionNode *pMutexNode;
    g_uMutexNum = 0;

    ForEachDLinkNode(MutexDetectionNode *, pMutexNode, &g_usedMutexListHead) {
        g_mutexDect[g_uMutexNum++] = pMutexNode->pMutex;
    }
}

_ELASTOS Boolean IsInThreadDectPool(Thread *pThread)
{
    for (UInt32 i = 0; i < g_uThreadNum; i++) {
        if (g_threadDect[i] == pThread) return TRUE;
    }

    return FALSE;
}

void NumberedDetectionThreads()
{
    Thread *pCurThread = GetCurrentThread();
    assert(pCurThread != NULL);

    g_uThreadNum = 0;
    g_threadDect[g_uThreadNum++] = pCurThread;

    MutexDetectionNode *pMutexNode;

    ForEachDLinkNode(MutexDetectionNode *, pMutexNode, &g_usedMutexListHead) {
        Thread *pThread = pMutexNode->pMutex->GetOwner();
        if (pThread && !IsInThreadDectPool(pThread)) {
            g_threadDect[g_uThreadNum++] = pThread;
        }

        uint32_t uFlags = SaveFlagsAndCli();
        DLinkNode *pWaitThreadListHead = pMutexNode->pMutex->GetWaitListHead();
        ForEachDLinkNode(Thread *, pThread, pWaitThreadListHead) {
            if (!IsInThreadDectPool(pThread)) {
                g_threadDect[g_uThreadNum++] = pThread;
            }
        }
        RestoreIF(uFlags);
    }
}

UInt32 GetMutexNum(DzMutex *pMutex)
{
    for (UInt32 i = 0; i < g_uMutexNum; i++) {
        if (g_mutexDect[i] == pMutex) return i;
    }

    return c_dlMutexMax;
}

UInt32 GetDectThreadNum(Thread *pThread)
{
    for (UInt32 i = 0; i < g_uThreadNum; i++) {
        if (g_threadDect[i] == pThread) return i;
    }

    return c_dlThreadMax;
}

DzMutex *GetRequestedMutex(Thread *pThread)
{
    MutexDetectionNode *pMutexNode;

    ForEachDLinkNode(MutexDetectionNode *, pMutexNode, &g_usedMutexListHead) {
        Thread *pth = NULL;

        uint32_t uFlags = SaveFlagsAndCli();
        DLinkNode *pWaitThreadListHead = pMutexNode->pMutex->GetWaitListHead();
        ForEachDLinkNode(Thread *, pth, pWaitThreadListHead) {
            if (pth == pThread) {
                RestoreIF(uFlags);
                return pMutexNode->pMutex;
            }
        }
        RestoreIF(uFlags);
    }

    return NULL;
}

void OutputDeadLockInfo(UInt32 *pArr)
{
    kprintf("\n");

    for (UInt32 i = 1; i < pArr[0] - 1; i++) {
        if ((i != 1) && (i % 2 == 0)) {
            kprintf(" ---> Mutex:%x ====> ", g_mutexDect[pArr[i]]);
        }
        else {
            kprintf("Thread:%x[%S]", g_threadDect[pArr[i]],
                ((Thread *)g_threadDect[pArr[i]])->m_wszName);
        }
    }

    kprintf("Thread:%x[%S]\n", g_threadDect[pArr[1]],
            ((Thread *)g_threadDect[pArr[1]])->m_wszName);
}

EXTERN void InitMutexDetection()
{
    g_freeMutexListHead.Initialize();
    g_usedMutexListHead.Initialize();

    for (UInt32 i = 0; i < c_dlMDetectNodeMax; i++) {
        g_freeMutexListHead.InsertLast(&g_mutexDetection[i]);
    }
}

#endif //MUTEX_DEADLOCK_DETECT
